Number of recent calls

Time: O(1)ONAVERAGE; Space: O(W); easy

Write a class RecentCounter to count recent requests.

It has only one method: ping(int t), where t represents some time in milliseconds.

Return the number of pings that have been made from 3000 milliseconds ago until now.

Any ping with time in [t - 3000, t] will count, including the current ping.

It is guaranteed that every call to ping uses a strictly larger value of t than before.

Example 1:

Input:

s = RecentCounter()
s.ping(1)
s.ping(100)
s.ping(3001)
s.ping(3002)

Output: [null,1,2,3,3]

Notes:

  • Each test case will have at most 10000 calls to ping.

  • Each test case will call ping with strictly increasing values of t.

  • Each call to ping will have 1 <= t <= 10^9.

1. Queue

Intuition

We only care about the most recent calls in the last 3000 ms, so let’s use a data structure that keeps only those.

Algorithm

  • Keep a queue of the most recent calls in increasing order of t.

  • When we see a new call with time t, remove all calls that occurred before t - 3000.

[5]:

import collections

class RecentCounter(object):
    """
    Time: O(Q), where Q is the number of queries made.
    Space: O(W), where W = 3000 is the size of the window we should scan for recent calls.
           In this problem, the complexity can be considered O(1).
    """
    def __init__(self):
        self.__q = collections.deque()

    def ping(self, t):
        """
        :type t: int
        :rtype: int
        """
        self.__q.append(t)
        while self.__q[0] < t-3000:
            self.__q.popleft()
        return len(self.__q)

[6]:

s = RecentCounter()
assert s.ping(1)    == 1
assert s.ping(100)  == 2
assert s.ping(3001) == 3
assert s.ping(3002) == 3